package codingforgreat.lchot150;

//indexTree 2D
public class Lc308 {
    public class IndexTree2D{
        public int[][] tree;
        public int[][] nums;
        public int N;
        public int M;
        public IndexTree2D(int[][] grid) {
            if(grid == null || grid.length == 0 || grid[0].length == 0){
                return;
            }
            N = grid.length;
            M = grid[0].length;
            tree = new int[N + 1][M + 1];
            nums = new int[N][M];
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    update(i,j, grid[i][j]);
                }
            }
        }
        public void update(int row, int col, int val){
            if(N == 0 || M == 0){
                return;
            }
            nums[row][col] = val;
            for(int i = row + 1;i <= N;i += i & (-i)){
                for(int j = col + 1;j <= M;j += j & (-j)){
                    tree[i][j] += val;
                }
            }
        }
        private int sum(int row, int col) {
            int sum = 0;
            for (int i = row + 1; i > 0; i -= i & (-i)) {
                for (int j = col + 1; j > 0; j -= j & (-j)) {
                    sum += tree[i][j];
                }
            }
            return sum;
        }
        public int sumRegion(int row1, int col1, int row2, int col2) {
            if (N == 0 || M == 0) {
                return 0;
            }
            return sum(row2,col2) - sum(row2,col1-1) - sum(row1-1,col2) + sum(row1-1,col1-1);
        }
    }
}
